Beware of the cheap hostels near the bus offices. If you arrive in the early morning these places will charge you a full night for your stay until 12PM noon.
Hotel Avenida
Ferroviaria 11, 693-2078 (http://www.boliviahostels.com), clean and inexpensive in the town center, near tour operators. only two hot showers, but the door to one is often locked. single 30bs, double/matrimonial 60bs u$s 9, with bath 100bs u$s 14.
Hostal Sajama
Potosã 35, 693-3099. cheap place with basic clean rooms. single with shared / private bathroom bs.25 / bs.40. note! on may 30, 2007, two canadian students visiting uyuni were found dead in their rooms at this hostal due to carbon-monoxide poisoning from their gas heater. (http://news.yahoo.com/s/a...)